//给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。 
//
// 请返回层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中 最小 的那个。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：root = [1,7,0,7,-8,null,null]
//输出：2
//解释：
//第 1 层各元素之和为 1，
//第 2 层各元素之和为 7 + 0 = 7，
//第 3 层各元素之和为 7 + -8 = -1，
//所以我们返回第 2 层的层号，它的层内元素之和最大。
// 
//
// 示例 2： 
//
// 
//输入：root = [989,null,10250,98693,-89388,null,null,null,-32127]
//输出：2
// 
//
// 
//
// 提示： 
//
// 
// 树中的节点数在
// [1, 10⁴]范围内
// 
// -10⁵ <= Node.val <= 10⁵ 
// 
//
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树 👍 73 👎 0

package leetcode.editor.cn;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class _1161_MaximumLevelSumOfABinaryTree {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
//        System.out.println(new TreeNode().val);

        Solution solution = new _1161_MaximumLevelSumOfABinaryTree().new Solution();
//        TreeNode root = new TreeNode(1, new TreeNode(7, new TreeNode(7), new TreeNode(-8)), new TreeNode(0));
        TreeNode root = new TreeNode(-100, new TreeNode(-200, new TreeNode(-20), new TreeNode(-5)), new TreeNode(-300, new TreeNode(-10), null));
        System.out.println(solution.maxLevelSum(root));
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */

    /**
     * 官方的广度优先遍历
     */
    class Solution3 {
        public int maxLevelSum(TreeNode root) {
            Deque<TreeNode> queue = new ArrayDeque<>();
            queue.addLast(root);
            int res = 1;
            int maxSum = root.val;
            for (int level = 1; !queue.isEmpty(); level++) {
                Deque<TreeNode> nextQueue = new ArrayDeque<>();
                int sum = 0;
                while (!queue.isEmpty()) {
                    TreeNode node = queue.removeFirst();
                    sum += node.val;
                    if (node.left != null) nextQueue.addLast(node.left);
                    if (node.right != null) nextQueue.addLast(node.right);
                }
                if (sum > maxSum) {
                    res = level;
                    maxSum = sum;
                }
                queue = nextQueue;
            }
            return res;
        }
    }

    /**
     * 官方解法的深度优先遍历
     */
    class Solution2 {
        private List<Integer> sum = new ArrayList<>();

        public int maxLevelSum(TreeNode root) {
            dfs(root, 0);
            int ans = 0;
            for (int i = 0; i < sum.size(); i++) {
                if (sum.get(i) > sum.get(ans)) {
                    ans = i;
                }
            }
            return ans + 1;
        }

        private void dfs(TreeNode node, int level) {
            if (level == sum.size()) {
                sum.add(node.val);
            } else {
                sum.set(level, sum.get(level) + node.val);
            }
            if (node.left != null) {
                dfs(node.left, level + 1);
            }
            if (node.right != null) {
                dfs(node.right, level + 1);
            }
        }
    }

    class Solution {
        public int maxLevelSum(TreeNode root) {
            Deque<TreeNode> queue = new ArrayDeque<>();
            queue.addLast(root);
            final int NULL = 100001;
            TreeNode noThing = new TreeNode(NULL);
            queue.addLast(noThing);
            int max = -NULL;
            int sum = 0;
            int ceng = 1;
            int maxCeng = 1;
            while (!queue.isEmpty()) {
                TreeNode node = queue.removeFirst();
                if (node.val != NULL) {
                    sum += node.val;
                    if (node.left != null) queue.addLast(node.left);
                    if (node.right != null) queue.addLast(node.right);
                } else {
                    if (sum > max) {
                        max = sum;
                        maxCeng = ceng;
                    }
                    if (!queue.isEmpty()) {
                        queue.addLast(noThing);
                    }
                    sum = 0;
                    ceng++;
                }
            }
            return maxCeng;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}